﻿namespace _5._8._01.Assertions.Assertions
{
    using System;
    using System.Linq;
    using System.Diagnostics;

    class AssertionsExercise
    {
        public static void SelectionSort<T>(T[] arr) where T : IComparable<T>
        {
            for (int index = 0; index < arr.Length-1; index++)
            {
                int minElementIndex = FindMinElementIndex(arr, index, arr.Length - 1);
                Swap(ref arr[index], ref arr[minElementIndex]);
            }

            Debug.Assert(IsSorted(new[] { 1, 2, 2, 4 }), "The IsSorted check is not working");
            Debug.Assert(IsSorted(arr), "The array is not sorted");
        }

        private static bool IsSorted<T>(T[] arr) where T: IComparable<T>
        {
            for (int i = 0; i < arr.Length - 1; i++)
            {
                if (arr[i].CompareTo(arr[i + 1]) > 0)
                {
                    return false;
                }
            }

            return true;
        }
  
        private static int FindMinElementIndex<T>(T[] arr, int startIndex, int endIndex)
            where T : IComparable<T>
        {
            Debug.Assert(arr != null, "The array does not have reference (is null)");
            Debug.Assert(arr.Length > 0, "The array cannot be empty");
            Debug.Assert(startIndex >= 0 && startIndex < arr.Length, "The startIndex is out of range");
            Debug.Assert(
                endIndex >= 0 && endIndex < arr.Length,
                "The endIndex is out of range",
                "This should be a second detailed explaination of the current case");
            Debug.Assert(
                startIndex <= endIndex,
                "startIndex must be greater than endIndex",
                "startIndex is {0}, endIndex is {1}", startIndex, endIndex);

            int minElementIndex = startIndex;

            for (int i = startIndex + 1; i <= endIndex; i++)
            {
                if (arr[i].CompareTo(arr[minElementIndex]) < 0)
                {
                    minElementIndex = i;
                }
            }

            Debug.Assert(
                new Func<bool>(() =>
                {
                    for (int i = startIndex; i <= endIndex; i++)
                    {
                        if (arr[minElementIndex].CompareTo(arr[i]) > 0)
                        {
                            return false;
                        }
                    }

                    return true;
                })(),
                "The found element does not have the smallest value");

            return minElementIndex;
        }

        private static void Swap<T>(ref T x, ref T y)
        {
            T oldX = x;
            x = y;
            y = oldX;
        }

        public static int BinarySearch<T>(T[] arr, T value) where T : IComparable<T>
        {
            return BinarySearch(arr, value, 0, arr.Length - 1);
        }

        private static int BinarySearch<T>(T[] arr, T value, int startIndex, int endIndex) 
            where T : IComparable<T>
        {
            Debug.Assert(arr != null, "The array does not have reference (is null)");
            Debug.Assert(arr.Length > 0, "The array cannot be empty");
            Debug.Assert(startIndex >= 0 && startIndex < arr.Length, "The startIndex is out of range");
            Debug.Assert(
                endIndex >= 0 && endIndex < arr.Length,
                "The endIndex is out of range",
                "This should be a second detailed explaination of the current case");
            Debug.Assert(
                startIndex <= endIndex,
                "startIndex must be greater than endIndex",
                "startIndex is {0}, endIndex is {1}",
                startIndex,
                endIndex);
            Debug.Assert(IsSorted(arr), "The array is not sorted");
            Debug.Assert((long)(startIndex + endIndex) > int.MaxValue, "The algorithm overflows Int32");

            int startIndexBackupForAssert = startIndex;
            int endIndexBackupForAssert = endIndex;

            while (startIndex <= endIndex)
            {
                int midIndex = (startIndex + endIndex) / 2;

                if (arr[midIndex].Equals(value))
                {
                    return midIndex;
                }

                if (arr[midIndex].CompareTo(value) < 0)
                {
                    // Search on the right half
                    startIndex = midIndex + 1;
                }
                else 
                {
                    // Search on the right half
                    endIndex = midIndex - 1;
                }
            }

            Debug.Assert(
                ((Func<bool>)(() =>
                {
                    for (int i = startIndexBackupForAssert; i <= endIndexBackupForAssert; i++)
                    {
                        if (arr[i].Equals(value))
                        {
                            return false;
                        }
                    }

                    return true;
                }))(),
                "The algorithm missed to find the searched value");

            // Searched value not found
            return -1;
        }

        static void Main()
        {
            int[] arr = new int[] { 3, -1, 15, 4, 17, 2, 33, 0 };
            Console.WriteLine("arr = [{0}]", string.Join(", ", arr));
            SelectionSort(arr);
            Console.WriteLine("sorted = [{0}]", string.Join(", ", arr));

            SelectionSort(new int[0]); // Test sorting empty array
            SelectionSort(new int[1]); // Test sorting single element array

            Console.WriteLine(BinarySearch(arr, -1000));
            Console.WriteLine(BinarySearch(arr, 0));
            Console.WriteLine(BinarySearch(arr, 17));
            Console.WriteLine(BinarySearch(arr, 10));
            Console.WriteLine(BinarySearch(arr, 1000));
        }
    }
}